

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

A$^*$ Search

The module Set implements sets as AVL trees. The API provided by Set offers the following functions and methods:

Set() creates an empty set.
S.isEmpty() checks whether the set Sis empty.
S.member(x) checks whether x is an element of the set S.
S.insert(x) inserts x into the set S. This does not return a new set but rather modifies the set S.
S.delete(x) deletes x from the set S. This does not return a new set but rather modifies the set S.
S.pop() returns the smallest element of the set S. Furthermore, this element is removed from S. Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if x and y are inserted into a set, then the expression x < y must return a Boolean value and < has to define linear order.

The module Set can be used to implement a priority queue that supports the removal of elements.



In [ ]:

    
import Set

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
heuristic is a function that takes two states as arguments. It returns an estimate of the length of the shortest path between these states. If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$

The function search implements A$^*$ search.



In [ ]:

    
def search(start, goal, next_states, heuristic):
    Parent   = { start:start }
    Distance = { start: 0 }           
    estGoal  = heuristic(start, goal)
    Estimate = { start: estGoal }
    Frontier = Set.Set()
    Frontier.insert( (estGoal, start) )
    while not Frontier.isEmpty():
        estimate, state = Frontier.pop()
        if state == goal:
            print(len(Estimate))
            return path_to(state, Parent)
        stateDist = Distance[state]
        for ns in next_states(state):
            oldEstimate = Estimate.get(ns, None)
            newEstimate = stateDist + 1 + heuristic(ns, goal)
            if oldEstimate == None or newEstimate < oldEstimate:
                Distance[ns] = stateDist + 1
                Estimate[ns] = newEstimate
                Parent[ns]   = state
                Frontier.insert( (newEstimate, ns) )
                if oldEstimate != None:
                    Frontier.delete( (oldEstimate, ns) )

Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.



In [ ]:

    
def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]

Lets draw the start state and animate the solution that has been found.



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: